<!DOCTYPE HTML>
<html lang="zh-CN">

<head><meta name="generator" content="Hexo 3.9.0">
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><!--Setting-->
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
    <meta http-equiv="Cache-Control" content="no-siteapp">
    <meta http-equiv="Cache-Control" content="no-transform">
    <meta name="renderer" content="webkit|ie-comp|ie-stand">
    <meta name="apple-mobile-web-app-capable" content="AncyBlog">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="format-detection" content="telephone=no,email=no,adress=no">
    <meta name="browsermode" content="application">
    <meta name="screen-orientation" content="portrait">
    <meta name="theme-version" content="1.2.3">
    <meta name="root" content="/">
    <link rel="dns-prefetch" href="http://www.anciety.de">

    <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <!--SEO-->

<meta name="keywords" content="learning,function programming">


<meta name="description" content="浅谈函数式编程
前言
关于这个话题我其实很早以前就想聊一聊，但是鉴于自己水平有限，一直不敢瞎说，比较担心说错或是理解不够深刻，但是换个角度想，这反正只是我的理解，如果不发出来也不知道错了还是没错...">


<meta name="robots" content="all">
<meta name="google" content="all">
<meta name="googlebot" content="all">
<meta name="verify" content="all">
    <!--Title-->

<title>
    
    浅谈函数式编程（1） |
    
    AncyBlog
</title>

<link rel="alternate" href="/atom.xml" title="AncyBlog" type="application/atom+xml">


<link rel="icon" href="/favicon.png">

    

<link rel="stylesheet" href="/css/bootstrap.min.css?rev=3.3.7">
<link rel="stylesheet" href="/css/font-awesome.min.css?rev=4.7.0">
<link rel="stylesheet" href="/css/style.css?rev=@@hash">
    



<script type="text/javascript" src="https://tajs.qq.com/stats?sId=66471611" charset="UTF-8"></script><!-- hexo-inject:begin --><!-- hexo-inject:end -->


    

</head>
</html>
<!--[if lte IE 8]>
<style>
    html{ font-size: 1em }
</style>
<![endif]-->
<!--[if lte IE 9]>
<div style="ie">你使用的浏览器版本过低，为了你更好的阅读体验，请更新浏览器的版本或者使用其他现代浏览器，比如Chrome、Firefox、Safari等。</div>
<![endif]-->
<body>
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><header class="main-header"  style="background-image:url(
    https://www.anciety.de/img/banner.jpg)"
     >
    <div class="main-header-box">
        <a class="header-avatar" href="/" title='Anciety'>
            <img src="/img/avatar.jpg" alt="logo头像" class="img-responsive center-block">
        </a>
        <div class="branding">
            <!--<h2 class="text-hide">Snippet主题,从未如此简单有趣</h2>-->
            
            <h2>
                Hacked By Swing
            </h2>
            
        </div>
    </div>
</header>
    <nav class="main-navigation">
    <div class="container">
        <div class="row">
            <div class="col-sm-12">
                <div class="navbar-header"><span class="nav-toggle-button collapsed pull-right" data-toggle="collapse" data-target="#main-menu" id="mnav">
                        <span class="sr-only"></span>
                        <i class="fa fa-bars"></i>
                    </span>
                    <a class="navbar-brand" href="http://www.anciety.de">
                        AncyBlog</a>
                </div>
                <div class="collapse navbar-collapse" id="main-menu">
                    <ul class="menu">
                        
                        <li role="presentation" class="text-center">
                            <a href="/"><i class="fa "></i>
                                首页</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/writeups/"><i class="fa "></i>
                                writeups</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/学习/"><i class="fa "></i>
                                学习</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/问题解决/"><i class="fa "></i>
                                问题解决</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/categories/扯淡/"><i class="fa "></i>
                                扯淡</a>
                        </li>
                        
                        <li role="presentation" class="text-center">
                            <a href="/archives/"><i class="fa "></i>
                                时间轴</a>
                        </li>
                        
                    </ul>
                </div>
            </div>
        </div>
    </div>
</nav>
    <section class="content-wrap">
        <div class="container">
            <div class="row">
                <main class="col-md-8 main-content m-post">
                    <p id="process"></p>
<article class="post">
    <div class="post-head">
        <h1 id="浅谈函数式编程（1）">
            
            浅谈函数式编程（1）
            
        </h1>
        <div class="post-meta">
    
    <span class="categories-meta fa-wrap">
        <i class="fa fa-folder-open-o"></i>
        <a class="category-link" href="/categories/学习/">学习</a>
    </span>
    
    
    <span class="fa-wrap">
        <i class="fa fa-tags"></i>
        <span class="tags-meta">
            
            <a class="tag-link" href="/tags/function-programming/">function programming</a> <a class="tag-link" href="/tags/learning/">learning</a>
            
        </span>
    </span>
    
    
    
    <span class="fa-wrap">
        <i class="fa fa-clock-o"></i>
        <span class="date-meta">
            2019/11/05</span>
    </span>
    
    <span class="fa-wrap">
        <i class="fa fa-eye"></i>
        <span id="busuanzi_value_page_pv"></span>
    </span>
    
    
</div>
        
        
    </div>
    
    <div class="post-body post-content">
        <h1 id="浅谈函数式编程">浅谈函数式编程</h1>
<h2 id="前言">前言</h2>
<p>关于这个话题我其实很早以前就想聊一聊，但是鉴于自己水平有限，一直不敢瞎说，比较担心说错或是理解不够深刻，但是换个角度想，这反正只是我的理解，如果不发出来也不知道错了还是没错，所以还是决定写一下，如果有错漏也欢迎指出，理解不对的也欢迎探讨。（我可能会简化一些东西便于理解）</p>
<p>另外，本文在写的时候是认为大家对写程序有一定理解的，所以我会假设大家已经会一种或者多种语言，我会尽量使用较为普及的语言来解释。但是如果你完全没有编程基础，这不是一篇入门的教程，可能会存在阅读上的困难。</p>
<h2 id="生活太简单了加点难度">生活太简单了，加点难度。</h2>
<p>让我们做个假设，假设有一天，你写代码的时候觉得写代码实在太简单了，于是决定给自己加点难度。</p>
<p>这个难度怎么加呢？代码还是要写的，逻辑还是得要的，但是你就是突然太讨厌变量了。于是你决定从此以后你用的“变量”再也不给第二次赋值（变量不再可变）。</p>
<p>举个例子：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">a = <span class="number">1</span> <span class="comment"># 第一次赋值</span></span><br><span class="line">a = <span class="number">2</span> <span class="comment"># 第二次赋值，在今天以后，你决定再也不写这种代码了</span></span><br></pre></td></tr></table></figure>
<p>没有了赋值，你就不能再写循环了。为什么呢？让我们来看一种循环的实现方式：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">i = <span class="number">0</span></span><br><span class="line"><span class="keyword">while</span> i &lt; <span class="number">10</span>:</span><br><span class="line">    print(i)</span><br><span class="line">    i += <span class="number">1</span></span><br></pre></td></tr></table></figure>
<p>如果用 <code>C</code> 来写，就更显然了</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">10</span>; ++i) &#123;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, i);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为什么呢？因为你不能再 <code>i += 1</code> 或者 <code>i++</code>（<code>++i</code>）了。（还记得你刚刚提高的难度么？）</p>
<p>没有了循环，代码还怎么写呢？</p>
<p>其实也不难，虽然没有了循环，但是你还可以用递归呀，所以我们可以把原来的循环代码改成这样：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">print_10</span><span class="params">(i)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> i &lt; <span class="number">10</span>:</span><br><span class="line">        print(i)</span><br><span class="line">        print_10(i + <span class="number">1</span>)</span><br></pre></td></tr></table></figure>
<p>C 语言也是一样：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print_10</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (i &lt; <span class="number">10</span>) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, i);</span><br><span class="line">        print_10(i + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>所以，用这样的方式，你依然可以写出原来能够写出的代码。那区别是哪儿呢？区别是你在使用“函数式编程了”。</p>
<h2 id="函数式编程">函数式编程</h2>
<p>到现在我们说到了函数式编程的其中两个原则：</p>
<ol type="1">
<li>没有变量，只有绑定（也就是只能有仅允许一次赋值或是叫做绑定的常量）</li>
<li>没有循环，只有递归</li>
</ol>
<p>另外我们还需要加上一点：</p>
<ol start="3" type="1">
<li>函数可以作为参数传入</li>
</ol>
<p>这一点由于在现行的大多数语言中已经支持了（例如 <code>Python</code>、<code>Javascript</code>等都已经支持了闭包，或者是匿名函数等）。</p>
<p>如果不去纠结细节，满足这几点，我们基本上已经在进行“函数式编程”了。</p>
<p>（事实上函数式编程涉及到 lambda 演算等理论，但是这里我们简化了一下，认为符合这几点就算函数式编程）</p>
<p>由于函数式编程的几个特点，编程时的思路也有些不同。由于函数可以作为参数传入，加上使用递归，在函数式编程中，我们往往倾向于编写大量“小的函数”，然后对函数进行组合来完成完整的程序。</p>
<h2 id="typeclass">Typeclass</h2>
<p>好了，我们知道了函数式编程，知道了函数式编程倾向于用小函数组合出完整程序。下面有一个问题，在普通的编程中（叫做指令式编程），我们可以采用面向对象的方式来尽量复用代码，函数编程中我们还可以使用这种方式吗？</p>
<p>当然不行。在面向对象中，我们没有要求对象“不可变”，也就是对象的状态（属性）是可以变的，那就不符合函数式编程的原则了。</p>
<p>所以我们该如何去复用代码呢？当然，要是能够尽力保持函数式编程的哲学（使用小函数组合成大函数）就更好了。</p>
<p>于是就有了 <code>typeclass</code>。</p>
<p>其实 <code>typeclass</code> 并不复杂，因为其实它基本上就是面向对象中的 <code>interface</code> ，接口。</p>
<p>接口规定了一个对象能够做的事情，我们如何应用接口来复用代码呢？其实不难，我们如果能把代码写在接口里，不就可以复用代码了吗？</p>
<p>比如：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">interface GetArea &#123;</span><br><span class="line">  method area(): Double</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">interface DoubleArea &#123;</span><br><span class="line">  // 不同的 area 我们都可以将它 * 2 ！</span><br><span class="line">  method double_area(): Double &#123;</span><br><span class="line">    this.area() * 2</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看到，无论具体的 <code>area</code> 是如何实现的，<code>double_area</code> 都可以利用 <code>area</code> 来完成他的功能，不同的 <code>area</code> 实现对应的 <code>double_area</code> 的结果也不一样。通过这样的方法，我们就可以将可以复用的代码实现在接口里。 （其实这也是另一种“面向对象”，Rust 语言就采用这样的面向对象，将 interface 命名为 trait）</p>
<p>如果我们要再 “typeclass” 一点，我们就不让接口和 “对象” 绑定，也就是说，我们调用 <code>area</code> 或者 <code>double_area</code> 的方式不是 <code>obj.area()</code> 或是 <code>obj.double_area()</code>，那我们要如何调用呢？</p>
<p>我们以 <code>double_area</code> 为例，不用这种方式调用之后，它就变为了 <code>double_area(obj)</code>，也就是应该传入一个参数，这个参数是我们希望计算出面积的对象（或是结构体等类似概念）。此时，<code>double_area</code> 对 <code>area</code> 的调用也变为了 <code>area(obj)</code> ，那如何去知道这个 <code>area</code> 是具体哪个 <code>area</code> 呢？</p>
<p>按照 <code>typeclass</code>，这个问题的答案就是：“根据类型而定”。因为一个 <code>typeclass</code> 会指定一个类型，类似如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">//        类型</span><br><span class="line">typeclass Circle GetArea &#123;</span><br><span class="line">  function area(circle: Circle): Double &#123;</span><br><span class="line">    // 实现</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">typeclass Circle DoubleArea &#123;</span><br><span class="line">  function double_area(circle: Circle): Double &#123;</span><br><span class="line">    // 由于这里的“circle”是 Circle类型，所以会使用 Circle 的 area 实现</span><br><span class="line">    circle.area() * 2</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>所以类型，是一个关键。</p>
<h2 id="几种-typeclasssemigroup">几种 typeclass：Semigroup</h2>
<p>接下来我们就需要看看几个关键的 <code>typeclass</code> 或者说 <code>interface</code>(<code>trait</code>) 了。这些 <code>typeclass</code> 的存在才使得函数式编程可以通过组合小函数来完成更多的任务。在我看来，这些“typeclass”组成了函数式编程的“设计模式”。</p>
<p>从这几种 <code>typeclass</code> 的介绍中我们就可以感受到函数式编程的模式中，低粒度的代码复用。</p>
<p>第一种是 Semigroup。</p>
<p>由于函数式编程和数学有一些的相关性，不少名词都来源于数学，然而事实上不完全明白这些数学概念也不会特别影响使用。</p>
<p>Semigroup 在数学中的意思是半群，这里沿用了其在数学中的定义。</p>
<p>这个 typeclass 需要一个“加法”，或者叫做结合，或者类似的意思，反正就是一个操作（我们这里用 "combine" 表示）（伪代码）：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">typeclass Semigroup &#123;</span><br><span class="line">  function combine(one: Semigroup, another: Semigroup): Semigroup;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>很明显，这是一个二元运算，要求运算的两个是同一个类型（这里由于我不想引入泛型的表示方式，所以伪代码中看不出来），且这个类型需要满足一个特定要求：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">combine(A, combine(B, C)) == combine(combine(A, B), C)</span><br></pre></td></tr></table></figure>
<p>看起来眼熟？是的，这就是数学上的结合律！在数学上半群其实定义与之类似，所以我们采用了这个命名。</p>
<p>然后？然后就没了。这个“接口”(typeclass) 就只需要这样的要求。</p>
<p>体会到函数式的特点了吗？粒度很细，如果说的更专业一点，这个叫做“抽象程度更高”（因为符合这个要求的情况更多）。</p>
<p>那么有哪些东西符合这个要求呢？例如，python中，字符串的连接：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">(<span class="string">"a"</span> + <span class="string">"b"</span>) + <span class="string">"c"</span> == <span class="string">"a"</span> + (<span class="string">"b"</span> + <span class="string">"c"</span>) <span class="comment"># True，将 a, b, c 任意替换也成立</span></span><br></pre></td></tr></table></figure>
<p>列表的连接：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">([<span class="number">1</span>] + [<span class="number">2</span>]) + [<span class="number">3</span>] == [<span class="number">1</span>] + ([<span class="number">2</span>] + [<span class="number">3</span>]) <span class="comment"># True，将 1, 2, 3 任意替换也成立</span></span><br></pre></td></tr></table></figure>
<p>那这个东西有什么用呢？这个问题其实比较难以回答，他的目的就是把你的数据结构和操作只要符合这个要求，就实现这个接口，然后我就可以很方便的组合出更高级的函数。</p>
<p>举个例子，比如我写一个函数，目的是把一个东西重复两次，我就可以用上这个“半群”。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">function mult2(s: Semigroup): Semigroup &#123;</span><br><span class="line">  combine(s, s)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>那这个函数可以干嘛呢？这个函数，如果我给他一个字符串，他就会把字符串重复两次，如果是列表，就会把元素重复两次，如果是数字，就会乘 2 ，这种函数非常“抽象”，函数式编程的特点就是这样，你通过组合一大堆十分“抽象”的函数，得到一个你想要的，你提供给别人的函数可能也十分抽象，这就是一种细粒度的组合。</p>
<p>这样写出的程序十分灵活，复用程度也很高，因为他们很“抽象”，他们可以在很多时候被反复使用，这就达到了代码复用的目的。</p>
<h2 id="typeclass-monoid">Typeclass: Monoid</h2>
<p>下一个是 Monoid，幺半群（也叫单位半群），同样来源于数学中的概念，名字十分高深，令人疑惑。</p>
<p>但是其实呢？它的要求也很简单。</p>
<p>首先它要求 Semigroup 要求的所有东西，也就是有一个满足结合律的二元运算。</p>
<p>接下来，它还额外需要一个函数，或者说，额外需要一个“元素”：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">typeclass Monoid: Semigroup &#123;</span><br><span class="line">  function empty(): Monoid;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>听名字就知道，这个东西代表“空”，或者说是零，或者单位，更准确（单位半群的单位，幺半群的幺元）。</p>
<p>和之前的半群一样，这个函数（或者元素，因为这个函数直接返回一个元素/对象）除了满足接口的要求，还需要额外满足一个定律：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">combine(empty(), A) == combine(A, empty()) == A</span><br></pre></td></tr></table></figure>
<p>想到什么了？对比一下我们学的数学：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">0 + A = A + 0 = A</span><br><span class="line">1 * A = A * 1 = A</span><br></pre></td></tr></table></figure>
<p>同样的，在实际程序中也有这样的例子。例如 Python 中的字符串：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">""</span> + A == A + <span class="string">""</span> == A</span><br></pre></td></tr></table></figure>
<p>还有列表：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">[] + A == A + [] == A</span><br></pre></td></tr></table></figure>
<p>所以，空字符串和空列表就是这里的 <code>empty</code> 应该返回的内容，然后字符串连接和空字符串、列表加法和空列表就形成了两个 Monoid （因为他们符合了这个要求）。</p>
<h2 id="typeclass-functor">Typeclass: Functor</h2>
<p>接下来我们来看一个非常具有特色的 typeclass ， functor ， 函子。这个的来源同样是数学，只不过就更高级一些了，来源于范畴论，所以我们不需要去深究他的来源了。</p>
<p>我们来看看他的要求，他的要求也足够抽象，也就是足够简单。在之前我们都没有用到“泛型”，现在我们必须要用泛型了，所以首先介绍一下什么是泛型。其实有 C++ 经验的同学应该是知道的，泛型，或者叫做类型参数，就是用一个“形式参数”代表一个类型。</p>
<p>举个例子：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">function combine&lt;T&gt;(a: T, b: T): T;</span><br></pre></td></tr></table></figure>
<p>这是之前我们提到的 Semigroup 的 <code>combine</code> 函数的正确写法（伪代码），其中 <code>&lt;T&gt;</code> 的意思是我们暂时不知道 <code>T</code> 是什么具体类型，于是用一个形式参数代替，等到使用这个函数的时候，根据传入的参数，来决定 T 是什么类型。假设我调用这个函数如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">combine(1, 2) // 1: Int</span><br></pre></td></tr></table></figure>
<p>那么 T 就是 Int。</p>
<p>另外一个记法是 <code>&lt;T: A&gt;</code>，这里 A 是某一个 typeclass，比如 Semigroup，那就写作 <code>&lt;T: Semigroup&gt;</code>，代表现在还不知道的类型 T 是什么类型，但是我们要求使用的时候（调用的时候），这个类型必须要满足 <code>Semigroup</code> 的要求，也就是这个类型 T 得有 <code>combine</code> 函数。</p>
<p>好了，我们现在来写写之前两个 typeclass 的正确写法：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">// 这里我们把类型参数移到了 typeclass 这，意思是整个 typeclass 内都是这一个类型参数</span><br><span class="line">typeclass Semigroup&lt;T&gt; &#123;</span><br><span class="line">  function combine(a: T, b: T): T;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">// 主要是在这里，我们需要 Semigroup 和 Monoid 中的 T 应该是同一个 T</span><br><span class="line">typeclass Monoid&lt;T&gt;: Semigroup&lt;T&gt; &#123;</span><br><span class="line">  function empty(): T;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>有了泛型，还不太够，为了表示 Functor，我们还需要一个东西，叫做“类型构造子”。</p>
<p>其实类型构造子我们早就见过，只不过我们需要给他们起一个名字。我们见过什么类型构造子呢？例如，python 中的列表……</p>
<p>他们是什么呢？他们将类型“包”了一层，比如我们要表达列表的类型，应该怎么表达呢？嗯，可以是“int 类型的列表”，“字符串类型的列表”……</p>
<p>发现什么了吗？他们的“里边”包含了类型，我们这里用 <code>A of B</code> 来表示类型构造子，例如 <code>List of Int</code>。</p>
<p>现在我们就可以来表达 Functor 了，我这里使用 <code>-&gt;</code> 来表示函数，箭头前为参数，后为返回值：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">typeclass Functor&lt;F&gt; &#123;</span><br><span class="line">  function map&lt;A, B&gt;(a: A, f: A -&gt; B): F of B;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个 typeclass 就比较有意思了，也有一些复杂，我们来仔细分析一下。</p>
<p>首先，整个函子需要一个 F 类型，根据他的用法（<code>F of B</code>），看来他是一个类型构造子，然后两个类型，分别是 A 和 B，接收一个类型 A 的变量，然后一个函数，传入类型 A 得到一个 B 类型返回值，最终返回一个 F of B。</p>
<p>嗯，好乱，看不懂。那我们来看一个“生活中的实例”吧：（python）</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">map(<span class="keyword">lambda</span> x: x + <span class="number">1</span>, [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]) <span class="comment"># == [2, 3, 4]</span></span><br></pre></td></tr></table></figure>
<p>哦？python 中也是 map ？是的，其实 python 的 map 就是这个 map ！</p>
<p>我们来看看，根据我们写的 typeclass ，类型 A 和 B 都是 Int，F 就是 List，函数就是这个匿名函数，最终得到一个 Int 列表 （<code>List of Int</code>）。</p>
<p>所以 Functor 在干什么呢？Functor 将类型构造子“包含”的那个类型“映射”成了另一个类型。</p>
<p>再举个例子：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">map(str, [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]) <span class="comment"># == ["1", "2", "3"]</span></span><br></pre></td></tr></table></figure>
<p>这里，就将 List 类型构造子内的 Int 映射成了 Str。</p>
<p>所以 Functor 的用处就是一种“映射”，例如在列表上，把列表“里”的东西映射成了另一种（例如都加一，或者变成字符串）。</p>
<p>我们在 python 中可以体会到这个 map 函数带来的好处，在列表上，相当于很自然的帮你做了一个循环（于是有好多“一行完成好多任务”的例子）。不仅如此，我们还可以进一步，思考一个实用的函数式编程模式。</p>
<h2 id="函数式中的option">函数式中的Option</h2>
<p>如何表达一个程序的返回值可有可无呢？很多编程语言都有自己的选择，例如在 Python 中用特殊值 <code>None</code> 来表示没有，Java 中用 <code>null</code>，C 语言用 <code>NULL</code> （其实是指针类型的 0）。</p>
<p>在 Functor 的讲解中，我们懂得了一个东西，叫做类型构造子，就像 List 。现在，我们扩展一下 Python 中用来表示“可有可无”的东西，用上我们的类型构造子，然后这个类型构造子命名为 Option。Option 包括两个值，一个 None，我们已经很熟悉了，另一个是一个特殊值，用来把一个值“包起来”，叫做 Some ，表示这个返回值存在。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">Option&lt;A&gt;:</span><br><span class="line">    Some(A)</span><br><span class="line">    None</span><br></pre></td></tr></table></figure>
<p>要是觉得 Some 不好理解，可以类比一下 <code>[]</code> 这个操作符。 Some 的一种用法：<code>Some(3)</code>，将一个 Int 值包起来，如果 Option 换成 List，就好比 <code>[3]</code>。</p>
<p>现在，让我们把我们之前所学的部分结合起来。</p>
<p>首先，这个 Option 类型构造子满足 Monoid 的要求，只要里边包含的 A 满足就可以，因为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">Some(A) + Some(B) == Some(A + B) // 这里就需要 A + B 满足 Semigroup 要求</span><br><span class="line">Some(A) + None == Some(A)</span><br><span class="line">None + Some(A) == Some(A)</span><br></pre></td></tr></table></figure>
<p>看到 Monoid 和 Semigroup 的用法了吗？empty 就是 None！我可以将加法变成内部的加法，这样我就从类型构造子“包含”的类型中，构造出了新的函数，然后这种构造几乎是不需要写额外代码的！（即使写也非常显然）</p>
<p>还不算完，如果再用上我们学到的 Functor：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">map(Some(A), f) == Some(f(A))</span><br><span class="line">map(None, f) == None</span><br></pre></td></tr></table></figure>
<p>这也是显然的！</p>
<p>那这有什么用？还记得一开始我们怎么提到 Option 的吗？是的，他可以用来表示“可有可无”，这意味着什么？</p>
<p>举个例子：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">positive_only</span><span class="params">()</span>:</span></span><br><span class="line">    a = int(input())</span><br><span class="line">    <span class="keyword">if</span> a &lt;= <span class="number">0</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">return</span> a</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add_two_inputs</span><span class="params">()</span>:</span></span><br><span class="line">    a = positive_only()</span><br><span class="line">    b = positive_only()</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> a == <span class="literal">None</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">    <span class="keyword">elif</span> b == <span class="literal">None</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">return</span> a + b</span><br></pre></td></tr></table></figure>
<p>这个的功能很简单，但是由于 <code>positive_only()</code> 一旦小于等于 0 则返回 None，导致在 <code>add_two_inputs()</code> 中需要写一个 if 来判断 None 的情况，如果有 Option 呢？</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">positive_only</span><span class="params">()</span>:</span></span><br><span class="line">    a = int(input())</span><br><span class="line">    <span class="keyword">if</span> a &lt;= <span class="number">0</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">return</span> Some(a)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add_two_inputs</span><span class="params">()</span>:</span></span><br><span class="line">    <span class="keyword">return</span> positive_only() + positive_only() <span class="comment"># 因为 Option 满足 Semigroup</span></span><br></pre></td></tr></table></figure>
<p>if 完全不再需要了！当然，这是由于加法的特殊性，那我们换一个：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 没有 Some</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">some_func</span><span class="params">()</span>:</span></span><br><span class="line">    a = positive_only()</span><br><span class="line">    b = positive_only()</span><br><span class="line">    <span class="keyword">if</span> a == <span class="literal">None</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">    <span class="keyword">elif</span> a &lt;= <span class="number">5</span>:</span><br><span class="line">        <span class="keyword">if</span> b == <span class="literal">None</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">6</span></span><br><span class="line"></span><br><span class="line"><span class="comment"># 有 Some</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">some_func</span><span class="params">()</span>:</span></span><br><span class="line">    a = positive_only()</span><br><span class="line">    b = positive_only()</span><br><span class="line">    <span class="comment"># 这里 map 的顺序 python 和我的伪代码有所不同，使用 python 的惯例</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">func</span><span class="params">(x)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> map(<span class="keyword">lambda</span> x: <span class="number">6</span>, b)</span><br><span class="line">    <span class="keyword">return</span> map(func, a)</span><br></pre></td></tr></table></figure>
<p>在 func 中，将返回常量 6 的函数 map 到 b 上，如果 b 是 None，那这个函数返回 None，否则返回常量 6， 之后这个函数 map 到 a 上，如果 a 是 None，那么不需要管 func 返回什么，都返回 None，否则返回 func 的返回值。所以这两个函数的效果是一样的（如果使用匿名函数，可以更简洁，但是相对难以阅读）。</p>
<p>于是有人问了，为什么要这么写？这么写明明思考起来更复杂啊？事实上这样的思考并不复杂，根据我们之前的规则，每一个 map 实际上都是将操作放到了里边包含的东西上，如果里边没有东西（None），那不管这个函数，我们直接返回 None，这么想其实写这样的代码就不复杂了。</p>
<p>这样写的一个最大好处：没有了边界判断！没有了“特设性假定”（误），没有特殊情况，于是我们的代码可以避免由于缺少特殊情况判断（忘记判断 None）而导致的问题。</p>
<h2 id="第一部分结语">第一部分结语</h2>
<p>这一部分我主要描述了函数式编程的基本概念，介绍了几个抽象方式，还有类型构造子、Functor 和 Option，其中类型构造子相对比较复杂，但是一旦理解就很简单了。</p>
<p>（本来打算一口气写完，但是似乎内容较多，一些内容我们下一步再写）</p>

    </div>
    
    <div class="post-footer">
        <div>
            
            转载声明：
            商业转载请联系作者获得授权,非商业转载请注明出处 © <a href="" target="_blank">Snippet</a>
            
            
        </div>
        <div>
            
        </div>
    </div>
</article>
<div class="article-nav prev-next-wrap clearfix">
    
    <a href="/2019/12/26/crypto_recap/" class="pre-post btn btn-default" title='密码学救命稻草'>
        <i class="fa fa-angle-left fa-fw"></i><span class="hidden-lg">上一篇</span>
        <span class="hidden-xs">
            密码学救命稻草</span>
    </a>
    
    
    <a href="/2019/10/08/afl/" class="next-post btn btn-default" title='AFL 浅读'>
        <span class="hidden-lg">下一篇</span>
        <span class="hidden-xs">
            AFL 浅读</span><i class="fa fa-angle-right fa-fw"></i>
    </a>
    
</div>

<div id="comments">
    

<div id="vcomments" class="valine"></div>
<!--<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="/assets/valine.min.js"></script>-->
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
<script>
new Valine({
    av: AV,
    el: '#vcomments',
    appId: 'sBJ8fsglfz3e3AeXQbE8d8H8-gzGzoHsz',
    appKey: 'WFXH17M73py6bGqWl0ffMbHG',
    placeholder: '说点什么吧',
    notify: false,
    verify: true,
    avatar: 'mm',
    meta: 'nick,mail'.split(','),
    pageSize: '10',
    path: window.location.pathname,
    lang: 'zh-CN'.toLowerCase()
})
</script>



</div>


                </main>
                
                    <aside id="article-toc" role="navigation" class="col-md-4">
    <div class="widget">
        <h3 class="title">
            文章目录
        </h3>
        
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#浅谈函数式编程"><span class="toc-text">浅谈函数式编程</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#前言"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#生活太简单了加点难度"><span class="toc-text">生活太简单了，加点难度。</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#函数式编程"><span class="toc-text">函数式编程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#typeclass"><span class="toc-text">Typeclass</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#几种-typeclasssemigroup"><span class="toc-text">几种 typeclass：Semigroup</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#typeclass-monoid"><span class="toc-text">Typeclass: Monoid</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#typeclass-functor"><span class="toc-text">Typeclass: Functor</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#函数式中的option"><span class="toc-text">函数式中的Option</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#第一部分结语"><span class="toc-text">第一部分结语</span></a></li></ol></li></ol>
        
    </div>
</aside>
                
            </div>
        </div>
    </section>
    <footer class="main-footer">
    <div class="container">
        <div class="row">
        </div>
    </div>
</footer>
<a id="back-to-top" class="icon-btn hide">
    <i class="fa fa-chevron-up"></i>
</a>
    <div class="copyright">
    <div class="container">
        <div class="row">
            <div class="col-sm-12">
                <div class="busuanzi">
    
    访问量:
    <strong id="busuanzi_value_site_pv">
        <i class="fa fa-spinner fa-spin"></i>
    </strong>
    &nbsp; | &nbsp;
    访客数:
    <strong id="busuanzi_value_site_uv">
        <i class="fa fa-spinner fa-spin"></i>
    </strong>
    
</div>
            </div>
            <div class="col-sm-12">
                <span>Copyright &copy;
                    2019
                </span> |
                <span>
                    Powered by <a href="//hexo.io" class="copyright-links" target="_blank" rel="nofollow">Hexo</a>
                </span> |
                <span>
                    Theme by <a href="//github.com/shenliyang/hexo-theme-snippet.git" class="copyright-links" target="_blank" rel="nofollow">Snippet</a>
                </span>
            </div>
        </div>
    </div>
</div>


<script src="/assets/tagcanvas.min.js?rev=2.9"></script>
<script>
var tagOption = {
    textColour: '#444', // 字体颜色
    outlineMethod: 'block', // 选中模式
    outlineColour: '#FFDAB9', // 选中模式的颜色
    interval: 30 || 30, // 动画帧之间的时间间隔，值越大，转动幅度越大
    textHeight: 13,
    outlineRadius: 3,
    freezeActive: true || '', // 选中的标签是否继续滚动
    frontSelect: true || '', // 不选标签云后部的标签
    initial: [0.1, -0.1],
    depth: 0.5,
    decel: 0.95,
    maxSpeed: 0.03,
    reverse: true || '', // 是否反向触发
    fadeIn: 500, // 进入动画时间
    wheelZoom: false || '' // 是否启用鼠标滚轮
}
TagCanvas.Start('tag-cloud-3d', '', tagOption);
</script>


<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<script src="/js/app.js?rev=@@hash"></script><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</body>
</html>